home *** CD-ROM | disk | FTP | other *** search
/ Celestin Apprentice 5 / Apprentice-Release5.iso / Source Code / PowerPlant / DMultiStringLocator / source / DMultiStringLocator.h < prev    next >
Text File  |  1996-07-02  |  4KB  |  121 lines
  1. // ===========================================================================
  2. // DMultiStringLocator.h
  3. //   ---------------------
  4. //   ©1996 Eric Gundrum, All rights reserved.
  5. //
  6. //   The contents of this file may be freely altered and freely distributed
  7. //   in any form, provided this copyright statement is retained unaltered.
  8. //   Add your own changes below.
  9. //   ---------------------
  10. //    
  11. //    Based on source code provided in Practical Algorithms for Programmers, 
  12. //    by Binstock and Rex, published in 1995 by Addison Wesley.
  13. //
  14. //    Simultaneously search text for multiple strings using the Aho/Corasick 
  15. //    algorithm.  
  16. //
  17.  
  18. #pragma once
  19.  
  20. // ANSI C++ headers
  21. // #include <stdexcept>
  22.  
  23. // Mac Headers
  24. #include <Types.h>    // for Boolean
  25.  
  26. // PowerPlant Headers
  27. #include <LList.h>
  28. #include <LString.h>
  29.  
  30.  
  31. #pragma mark --- DSearchString declarations ---
  32. // ===========================================================================
  33. // ----------- DSearchString declarations ----------
  34. // ===========================================================================
  35. //    An abstract class containing the string and identifying the function 
  36. //    called when this string is found.
  37.  
  38. class DSearchString    : public LStr255
  39. {
  40. public:
  41.     virtual                    ~DSearchString() {;}
  42.                              DSearchString() {;} 
  43.                             
  44.     virtual    Boolean            ReportFound( long /*inOffset*/ ) = 0;
  45.                             // inOffset indicates the location in the buffer 
  46.                             // of the last character of the recognized string.
  47.     
  48. private:
  49.                             // stop defaults
  50.                             DSearchString( const DSearchString &inOriginal );
  51.                             
  52. };
  53.  
  54.  
  55. #pragma mark --- DMultiStringLocator declarations ---
  56. // ===========================================================================
  57. // ----------- DMultiStringLocator declarations ----------
  58. // ===========================================================================
  59. class DMultiStringLocator
  60. {
  61. public:
  62.     virtual                    ~DMultiStringLocator();
  63.                             DMultiStringLocator
  64.                             ( LList &inStringList        // list of search strings
  65.                             , int inAlphabetSize = 256    // size of BranchTable
  66.                             );
  67.                             
  68.     virtual    int                SearchBuffer ( Uchar *inBufferP, int inSize );
  69.                             
  70.             class            error {};
  71.             class            memerror                : public error {};
  72.             class            state_table_exceeded    : public error {};
  73.             class            input_item_NULL            : public error {};
  74.             class            list_item_NULL            : public error {};
  75.             
  76.             enum            { searchStatus_stop = -1 };
  77.     
  78. protected:
  79.                             // stop defaults
  80.                             DMultiStringLocator( const DMultiStringLocator &inOriginal );
  81.                             DMultiStringLocator();
  82.                             
  83.             void            AddString ( DSearchString &inString );
  84.     typedef    int    stateT;
  85.             void            AddStateTrans
  86.                             ( int matchChar
  87.                             , stateT currentState
  88.                             , stateT nextState 
  89.                             );
  90.             void            RetryArrayInit();
  91.             void            FindRetryState
  92.                             ( int inChar, stateT currentState, stateT nextState );
  93.             
  94.             void            QueueAdd( int *queue, int gbeg, stateT inState );
  95.                 
  96.     stateT        mMaxState;                // max space for states
  97.     stateT        mHighState;                // track the next free state
  98.     int            mAlphabetSize;            // size of BranchTable
  99.     
  100.     int            *MatchArray;    // First level of matching:
  101.     #define    BRANCH        -1        // match flag: use branch table
  102.     #define    EMPTY_SLOT    -2        // match flag: unused slot
  103.  
  104.     #define    FAIL_STATE    -1        // for GototState and BranchTable
  105.     #define state_begin    0        // the starting state
  106.     
  107.     stateT        *RetryArray;    // jump to new search word (state) when search fails
  108.     
  109.     LList        *OutArray;        // results objects indexed by end state
  110.  
  111.     union GotoTable        // destination of MatchArray values
  112.     {
  113.         stateT    GotoState;        // destination if MatchArray is char
  114.         stateT    *BranchTable;    // else goto this BRANCH branch table
  115.     } *GotoArray;
  116. };
  117.  
  118.  
  119. // ===========================================================================
  120.  
  121.